class Solution(object):
    def minFallingPathSum(self, grid):
        m = len(grid)
        n = len(grid[0])
        st = [[grid[0][j], j] for j in range(n)]
        st.sort()
        for i in range(1, m):
            next_st = []
            for j in range(n):
                if j != st[0][1]:
                    next_st.append([st[0][0] + grid[i][j], j])
                else:
                    next_st.append([st[1][0] + grid[i][j], j])
            st = next_st
            st.sort()
        return st[0][0]


data = Solution()
grid = [[-73, 61, 43, -48, -36], [3, 30, 27, 57, 10], [96, -76, 84, 59, -15], [5, -49, 76, 31, -7],
        [97, 91, 61, -46, 67]]
print(data.minFallingPathSum(grid))
